package com.example.tencentTrain;

import java.util.Arrays;

/**
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。
 *  返回这三个数的和。假定每组输入只存在唯一答案。
 *
 *  示例：
 *  输入：nums = [-1,2,1,-4], target = 1
 * 输出：2
 * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
 */
public class Leetcode16_ThreeSumClosest {
    public static void main(String[] args) {
        int[] nums = {-1, 2, 1, -4};
        int target = 1;
        nums = new int[] {0, 2, 1, -3};
        target = 1;
//        new Solution().threeSumClosest(nums, target);
        // [1,2,4,8,16,32,64,128]
        //82
        nums = new int[] {1,2,4,8,16,32,64,128};
        target = 82;
        nums = new int[] {-1, 2, 1, -4};
        target = 1;
        // [-3,-2,-5,3,-4]
        //-1
        nums = new int[] {-3,-2,-5,3,-4};
        target = -1;
        System.out.println(new Solution().threeSumClosest(nums, target));
    }

    static class Solution {
        /**
         * 解法二:排序 + 双指针
         * 先排序
         * 首先考虑枚举第一个元素 a，对于剩下的两个元素 b 和 c，我们希望它们的和最接近 target − a。
         * 用 second、third 分别表示指向 b 和 c 的指针，
         * 初始时，second指向位置 i+1，即左边界；third指向位置 n-1，即右边界
         *   如果 a+b+c >= target，那么就将 third 向左移动一个位置；
         *   如果 a+b+c < target，那么就将 second向右移动一个位置。
         * @param nums
         * @param target
         * @return
         */
        private int threeSumClosest2(int[] nums, int target) {
            int res = Integer.MAX_VALUE - 100; // 不能初始为最大整数值(target为负数会溢出)
            Arrays.sort(nums);
            for (int first = 0; first < nums.length; first++) {
                if (first > 0 && nums[first] == nums[first - 1]) {
                    continue;
                }

                int third = nums.length - 1;
                int second = first + 1;
                while (second < third) {
                    int sum = nums[first] +nums[second] + nums[third];
                    if (sum == target) return sum;

                    if (Math.abs(sum - target) < Math.abs(res - target)) { // 当前三个数之和与target之间的距离比之前的小，更新res
                        res = sum;
                    }

                    if (sum > target) { // 如果和大于 target，移动 c 对应的指针
                        int tmp = third - 1;
                        // 移动到下一个不相等的元素
                        while (second < tmp && nums[tmp] == nums[third]) {
                            --tmp;
                        }
                        third = tmp;
                    } else {// 如果和小于 target，移动 b 对应的指针
                        int tmp = second + 1;
                        // 移动到下一个不相等的元素
                        while (tmp < third && nums[tmp] == nums[second]) {
                            ++tmp;
                        }
                        second = tmp;
                    }

                }
            }
            return res;
        }

        /**
         * 暴力法
         * 遍历三个数的所有组合，每次更新最接近target的三数之和的值
         * @param nums
         * @param target
         * @return
         */
        private int threeSumClosest1(int[] nums, int target) {
            int res = 0, distance = Integer.MAX_VALUE;
            for (int first = 0; first < nums.length; first++) {
                for (int second = first + 1; second < nums.length; second++) {
                    for (int third = second + 1; third < nums.length; third++) {
                        int sum = nums[first] + nums[second] + nums[third];
                        int tmpDis = Math.abs(sum - target);
                        if (tmpDis < distance) { // 三数之和和target的距离小于之前的就更新最终结果
                            distance = tmpDis;
                            res = sum;
                        }

                        if (distance == 0) return res; // 得到距离为0的数据后后面不可能还有比0更小的距离了
                    }
                }
            }

            return res;
        }

        public int threeSumClosest(int[] nums, int target) {
            return threeSumClosest2(nums, target);
        }
    }
}
